package com.leetcode.根据数据结构分类.图;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/1/13
 * @description: 684. 冗余连接
 * https://leetcode-cn.com/problems/redundant-connection/
 */
public class B_684_冗余连接 {

	public static void main(String[] args) {
		B_684_冗余连接 action = new B_684_冗余连接();
//		int[][] edges = {{1, 2}, {1, 3}, {2, 3}};
//		int[][] edges = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
		int[][] edges = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
//		int[][] edges = {{1, 3}, {3, 4}, {1, 5}, {3, 5}, {2, 3}};
//		int[][] edges = {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {1, 5}};
		int[] res = action.findRedundantConnection(edges);
		System.out.println("res = " + Arrays.toString(res));
	}


	/**
	 * 我的思路是：
	 * 1.列出顶点的度表；
	 * 2.寻找度最大的点
	 * 由于有下面这个限制，所以我的方案是有问题的！
	 * 如果有多个答案，则返回二维数组中最后出现的边
	 *
	 * @param edges
	 * @return
	 */
	public int[] findRedundantConnection_fail(int[][] edges) {
		//记录 数字以及对应的度
		HashMap<Integer, Integer> map = new HashMap<>();
		//作为数组的去重
		HashSet<int[]> set = new HashSet<>();
		for (int i = 0; i < edges.length; i++) {
			if (set.contains(edges[i])) {
				continue;
			}
			set.add(edges[i]);
			int from = edges[i][0];
			int to = edges[i][1];
			if (map.containsKey(from)) {
				map.put(from, map.get(from) + 1);
			} else {
				map.put(from, 1);
			}
			if (map.containsKey(to)) {
				map.put(to, map.get(to) + 1);
			} else {
				map.put(to, 1);
			}
		}

		Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
		Map.Entry<Integer, Integer> first = iterator.next();
		int min = first.getKey();
		//minSet 只有小于总数的时候才有意义
		HashSet<Integer> minSet = new HashSet<>();
		int max = min;
		HashSet<Integer> maxSet = new HashSet<>();
		minSet.add(min);
		maxSet.add(min);
		while (iterator.hasNext()) {
			Map.Entry<Integer, Integer> cur = iterator.next();
			if (cur.getValue() > map.get(max)) {
				max = cur.getKey();
				maxSet.clear();
				maxSet.add(cur.getKey());
			}
			if (cur.getValue().equals(map.get(max))) {
				maxSet.add(cur.getKey());
			}
			if (cur.getValue() < map.get(min)) {
				min = cur.getKey();
				minSet.clear();
				minSet.add(cur.getKey());
			}
			if (cur.getValue().equals(map.get(min))) {
				minSet.add(cur.getKey());
			}
		}
		for (int i = edges.length - 1; i >= 0; i--) {
			if (minSet.size() == map.size()) {
				if ((maxSet.contains(edges[i][0]))
						|| (maxSet.contains(edges[i][1]))) {
					return edges[i];
				}
			} else {
				if ((maxSet.contains(edges[i][0]) && !minSet.contains(edges[i][1]))
						|| (maxSet.contains(edges[i][1]) && !minSet.contains(edges[i][0]))) {
					return edges[i];
				}
			}
		}
		return new int[0];
	}


	/**
	 * 换一种思路
	 * 1.列出顶点的度表；
	 * 2.遍历 edges ，尝试删除，如果碰到度==1 ，就不能删
	 * --
	 * 思路依然不对
	 * --
	 * 还是考虑得不够全面，这种思路不对
	 *
	 * @param edges
	 * @return
	 */
	public int[] findRedundantConnection_fail2(int[][] edges) {
		//记录 数字以及对应的度
		HashMap<Integer, Integer> map = new HashMap<>();
		//作为数组的去重
		HashSet<int[]> set = new HashSet<>();
		for (int i = 0; i < edges.length; i++) {
			if (set.contains(edges[i])) {
				continue;
			}
			set.add(edges[i]);
			int from = edges[i][0];
			int to = edges[i][1];
			if (map.containsKey(from)) {
				map.put(from, map.get(from) + 1);
			} else {
				map.put(from, 1);
			}
			if (map.containsKey(to)) {
				map.put(to, map.get(to) + 1);
			} else {
				map.put(to, 1);
			}
		}

		for (int i = edges.length - 1; i >= 0; i--) {
			int from = edges[i][0];
			int to = edges[i][1];
			if (map.get(from) == 1 || map.get(to) == 1) {
				continue;
			}
			return edges[i];
		}
		return new int[0];
	}

	/**
	 * 换个并查集的思路：
	 * 1.通过遍历进行 union，直到所有的点的根节点都是一样的值：
	 * 2.//判断下一个节点是否为新的节点，如果不是那么这就是
	 * 判断本边是否减少了根节点的数量，如果没有，那它就是
	 * 【一条没有贡献的边】，也就是多了这条边造成了图中的环，
	 * 既然删除一条边就能完成无向无环树，那么这条边就是要删除的边
	 * --
	 * 难点：
	 * 1.如果快速得知 union find 中根节点个数
	 *
	 * @param edges
	 * @return
	 */
	public int[] findRedundantConnection(int[][] edges) {
		//1.找到元素的个数
		int len = edges.length;
		//元素的集合
		HashSet<Integer> itemSet = new HashSet<>();
		for (int i = 0; i < edges.length; i++) {
			itemSet.add(edges[i][0]);
			itemSet.add(edges[i][1]);
		}

		//记录上一个根节点的数量
		int lastRootNum = itemSet.size();
		//2.使用 union find
		InnerUnionFind unionFind = new InnerUnionFind(lastRootNum + 1);

//		itemSet.clear();
		//不能用 只有单一节点来进行判断，而是看根节点数量是否有变化
		//因为一开始存的就是所有不同的根节点
		//boolean onlyOneRoot = false;

		for (int i = 0; i < len; i++) {
			int from = edges[i][0];
			int to = edges[i][1];
			unionFind.union(from, to);

			if (lastRootNum == unionFind.rootSet.size()) {
				return edges[i];
			}
			lastRootNum = unionFind.rootSet.size();
//			if (onlyOneRoot) {
//				//此时已经判断出来 union find 只有一个根节点，
//				//那么需要判断此时是否有新的节点
//				if (itemSet.contains(from) && itemSet.contains(to)) {
//					return edges[i];
//				}
//			} else if (unionFind.rootSet.size() == 1) {
//				onlyOneRoot = true;
//			}

//			itemSet.add(from);
//			itemSet.add(to);

		}
		return new int[0];
	}

	/**
	 * 看了别人的题解，发现可以优化一下，关于：
	 * 如果找到那条没有作用的边！
	 * 即遍历到的 edge 的两个跟节点相同时，就是没有作用的时候！
	 * @param edges
	 * @return
	 */
	public int[] findRedundantConnection_faster(int[][] edges){
		int len = edges.length;
		//元素的集合
		HashSet<Integer> itemSet = new HashSet<>();
		for (int i = 0; i < edges.length; i++) {
			itemSet.add(edges[i][0]);
			itemSet.add(edges[i][1]);
		}
		InnerUnionFind unionFind = new InnerUnionFind(itemSet.size() + 1);
		for (int i = 0; i < len; i++) {
			int from = edges[i][0];
			int to = edges[i][1];
			if (unionFind.find(from) == unionFind.find(to)){
				return edges[i];
			}else {
				unionFind.union(from, to);
			}
		}
		return new int[0];
	}

	class InnerUnionFind {
		int[] parents;
		int[] rank;
		/**
		 * 记录 UnionFind 中的根节点
		 * 不考虑 0
		 */
		HashSet<Integer> rootSet = new HashSet<>();

		public InnerUnionFind(int capacity) {
			parents = new int[capacity];
			rank = new int[capacity];
			for (int i = 1; i < capacity; i++) {
				parents[i] = i;
				rootSet.add(i);
				rank[i] = 1;
			}
		}

		/**
		 * Path Compression
		 *
		 * @param index
		 * @return
		 */
		int find(int index) {
			if (index != parents[index]) {
				parents[index] = find(parents[index]);
			}
			return parents[index];
		}


		public void union(int index1, int index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			if (rank[index1] == rank[index2]) {
				//将 index1 嫁接到 index2
				parents[p1] = p2;
				//由于 p1 被合并，所以从 rootSet 中移除
				rootSet.remove(p1);
				rank[index2]++;
			} else if (rank[index1] < rank[index2]) {
				//矮的嫁接到 高的
				parents[p1] = p2;
				rootSet.remove(p1);
			} else {
				parents[p2] = p1;
				rootSet.remove(p2);
			}
		}
	}
}
